/**
 * 
 */
package com.jeearsenal.algorithm;

/**
 * @author monika
 *
 */
public class ArithmeticOperations {
	
	/**
	 * trims the leading zero.
	 * Example: 
	 * 	value = "000001", should return "1"
	 *  value = "000000", should return "0"
	 * @param value
	 * 
	 * @return the string with all unnecessary leading zero trimmed.
	 */
	public String trimLeadingZero(String value){
		if(value.length()<=0){
			return value;
		}
		if(value.charAt(0)!= '0'){
			return value;
		}else if(value.length() == 1){
			return value;
		}else{
			return trimLeadingZero(value.substring(1));
		}
	}
	
	/**
	 * to compare two numbers; assuming none of num1 and num2 is NULL.
	 * and numbers do not contain any leading zero, if it contains then
	 * we are ignoring that.
	 * 
	 * @param num1
	 * @param num2
	 * @return
	 * 		1  if num1 > num2
	 * 		0  if num1 = num2
	 * 		-1 if num1 < num2
	 */
	public int compare(String num1, String num2){
		num1 = trimLeadingZero(num1);
		num2 = trimLeadingZero(num2);
		int len1 = num1.length();
		int len2 = num2.length();
		if (len1 > len2){
			return 1;
		}else if(len2 > len1){
			return -1;
		}
		
		int index=0;
		int diff=0;
		while(index<len1 && index<len2){
			int n1 = num1.charAt(index);
			int n2 = num2.charAt(index);
			diff = n1 - n2;
			if(diff != 0){
				break;
			}
			index++;
		}
		if(diff > 0) return 1;
		if(diff < 0) return -1;
		return 0;
	}
	
	/**
	 * to add to very large (+ve) numbers.
	 * Assumption none of num1 and num2 is null.
	 * 
	 * @param num1
	 * @param num2
	 * @return
	 */
	public String add(String num1, String num2){
		num1 = trimLeadingZero(num1);
		num2 = trimLeadingZero(num2);
		/*if(num1 == null || num2==null){
			return "";
		}*/
		int len1 = num1.length();
		int len2 = num2.length();
		int index = 1;
		int carry = 0;
		StringBuffer result = new StringBuffer();
		while(index<=len1 || index<= len2) {
			int n1 = 0;
			int n2 = 0;
			if(index<=len1){
				n1 = num1.charAt(len1 - index)-'0';
			}
			if(index<=len2){
				n2 = num2.charAt(len2 - index)-'0';
			} 
			int sum = n1 + n2 + carry;
			carry = sum/10;
			result.append(sum%10);
			
			index++;
		}
		result = result.reverse();
		result.insert(0, carry);
		return trimLeadingZero(result.toString());
	}
	
	/**
	 * to subtract num2 from num1
	 * 
	 * @param num1
	 * @param num2
	 * @return (num1 - num2) if num1 >= num2; null otherwise.
	 */
	public String subtract(String num1, String num2){
		//System.out.println("----------------------");
		num1 = trimLeadingZero(num1);
		num2 = trimLeadingZero(num2);
		//System.out.println("Subtracting:"+num1+" - "+num2);
		int diff = compare(num1, num2);
		if(diff == 0){return "0";}
		if(diff < 0){return null;}
		
		int carry = 0;
		int index = 1;
		int len1 = num1.length();
		int len2 = num2.length();
		//System.out.println("len1="+len1+" len2="+len2);
		StringBuffer result = new StringBuffer();
		
		while(index <= len2){
			//System.out.println("Processing with index="+index);
			int n1 = num1.charAt(len1-index) - '0';
			int n2 = num2.charAt(len2-index) - '0';
			//System.out.println("n1="+n1+"\nn2="+n2+"\npre-carry="+carry);
			if(carry != 0){
				// this digit has given carry
				n1 = n1-1;
				carry--;
				//System.out.println("After pre-Carry processed; n1="+n1+" n2="+n2+" pre-carry="+carry);
			}
			if(n1<n2){
				// taking a carry
				n1 = n1 + 10;
				/* 
				 * if next digit had not donated a carry before,
				 * it should do that now.
				 */
				if(carry < 1){
					/*
					 * next digit should be able to give a carry.
					 * if its not, that digit itself should take carry
					 * and so on.
					 */
					int k = index + 1;
					int nextDigit = num1.charAt(len1- k) - '0';
					
					while(nextDigit <= 0) {
						// ideally nextDigit < 0 is not possible.
						carry++; // to be processed for next digit
						k++;
						nextDigit = num1.charAt(len1 - k) - '0';
					}
					carry++;
				}
			}
			result.append(n1-n2);
			//System.out.println("SubResult:"+result+"\ncarry="+carry);
			index++;
		}
		// Now process the remaining digits in num1.
		while(index <= len1){
			int n1 = num1.charAt(len1-index) - '0';
			if(carry > 0){
				if(n1 == 0){
					result.append("9");
				}else{
					result.append(n1-1);
				}
				carry--;
			}else{
				result.append(n1);
			}
			index++;
		}
		result = result.reverse();
		return trimLeadingZero(result.toString());
	}
	
	/**
	 * to multiply number represented by num1 with the magnitude of num2.
	 * we are concerned about magnitude, not the sign.
	 * 
	 * Note that num2 is an integer and need not be of single digit.
	 * 
	 * @param num1
	 * @param num2
	 * @return the product
	 */
	public String multiplyInt(String num1, int num2){
		if(num2<0){
			num2 = num2 * (-1);
		}
		if(num2 == 0){ return "0"; }
		int carry = 0;
		int index = 1;
		int len1 = num1.length();
		StringBuffer result = new StringBuffer();
		while(index <= len1){
			int n1 = num1.charAt(len1 - index) - '0';
			int prod = (n1 * num2) + carry;
			carry = prod / 10;
			result.append(prod%10);
			index++;
		}
		result = result.reverse();
		if(carry > 0){
			result.insert(0, carry);
		}
		return trimLeadingZero(result.toString());
		
	}
	
	/**
	 * to multiply two positive numbers
	 * 
	 * @param num1
	 * @param num2
	 * @return num1 * num2
	 */
	public String multiply(String num1, String num2) {
		num1 = trimLeadingZero(num1);
		num2 = trimLeadingZero(num2);
		if(num1 == null || num2 == null) {
			return null;
		}
		if(num1 == "0" || num2 == "0"){
			return "0";
		}
		int len1 = num1.length();
		String result = "0";
		for(int index=1;  index<= len1; index++){
			int n =  num1.charAt(len1-index) - '0';
			if(n != 0){
				String subResult = multiplyInt(num2,  n);
				if(subResult != "0"){
					/*
					 *  to add zeros to make 'subResult' equivalent to the place value of multiplier, n, 
					 */
					int count =  1;
					while(count < index){
						subResult = subResult + "0";
						count++;
					}
					result = add(result, subResult);
				}
			}
		}
		return trimLeadingZero(result);
	}
	
	/**
	 * to divide 'dividend' by the 'divisor'
	 * assuming both being positive.
	 * 
	 * @param dividend - string representing the dividend
	 * @param divisor - string representing the divisor
	 * @return an array of String only containing two elements
	 * 
	 * element[0] : quotient
	 * element[1] : remainder
	 */
	public String[] divide(String dividend, String divisor) throws ArithmeticException{
		divisor = trimLeadingZero(divisor);
		if(divisor.equalsIgnoreCase("0") == true){
			throw new ArithmeticException("/ by Zero is Not possible.");
		}
		dividend = trimLeadingZero(dividend);
		String result[] = divisionLogic(dividend, divisor);
		return result;
	}

	/*
	 * division algorithm
	 */
	private String[] divisionLogic(String dividend, String divisor) {
		//System.out.println("=======================================");
		//System.out.println("Dividend:"+dividend+"\nDivisor:"+divisor);
		String [] result = new String [2];
		int diff = compare(dividend, divisor);
		if(diff < 0){
			result[0] = "0";
			result[1] = dividend;
			return result;
		}
		if(diff == 0){
			result[0] = "1";
			result[1] = "0";
			return result;
		}
		result[0] = "";
		result[1] = "";
		String newDividend = dividend.substring(0, divisor.length());
		//System.out.println("newDIVIDEND:"+newDividend);
		for(int i=newDividend.length(); i<=dividend.length(); i++){
			//System.out.println("before loop: compare("+newDividend+","+ divisor+")= "+compare(newDividend, divisor));
			//System.out.println("i="+i);
			while(compare(newDividend, divisor) < 0 
					&& i < dividend.length()){
				result[0]= result[0]+"0";
				newDividend = newDividend + dividend.charAt(i);
				i++;
				//System.out.println("In loop newDIVIDEND:"+newDividend);
				//System.out.println("i="+i);
			}
			// System.out.println("After loop newDIVIDEND:"+newDividend);
			// System.out.println("i="+i);
			// System.out.println("compare("+newDividend+","+ divisor+")"+compare(newDividend, divisor));
			int quotient = 0;
			String prod = divisor;
			while(compare(newDividend, prod)>=0){
				quotient++;
				prod = multiplyInt(divisor, quotient+1);
			}
			prod = multiplyInt(divisor, quotient);
			// System.out.println("final maxQ:"+quotient+"\nprod:"+prod);
			if(quotient > 0){
				newDividend = subtract(newDividend, prod);
				result[0] = result[0] + quotient;
			}else{
				result[0] = result[0] + "0";
			}
			newDividend = trimLeadingZero(newDividend);
			// System.out.println("Before pulling down new digit newDIVIDEND:"+newDividend);
			if(newDividend == "0"){
				newDividend = "";
			}
			if(i<dividend.length()){
				newDividend = newDividend + dividend.charAt(i);
			}
			// System.out.println("After pulling down new digit newDIVIDEND:"+newDividend);
			// System.out.println("result[0]:"+result[0]);
			// System.out.println("result[1]:"+result[1]);
		}
		if(newDividend == ""){
			newDividend = "0";
		}
		result[1] = trimLeadingZero(newDividend);
		result[0] = trimLeadingZero(result[0]);
		// System.out.println("Final Quoteint:"+result[0]);
		// System.out.println("Remainder:"+result[1]);
		//System.out.println(multiply("457845869524558796321548796532694568", 7845692));
		return result;
	}	

}
